﻿namespace Leetcode.N0330;
public class Solution
{
    public int MinPatches(int[] nums, int n)
    {
        var count = 0;
        long max = 0;
        for (int i = 0; i < nums.Length && max < n; i++)
        {
            while (max < nums[i] - 1 && max < n)
            {
                count += 1;
                max = max * 2 + 1;
            }

            max += nums[i];
        }

        while (max < n)
        {
            count += 1;
            max = max * 2 + 1;
        }

        return count;
    }
}
